This invention relates to the detection of faults in a digital circuit. More particularly, this invention relates to a statistics-based method and apparatus for estimating the fault coverage of a set of test vectors applied to a digital circuit that contains sequential circuit elements.
Fault simulators, which are known in the art, allow a circuit designer to model manufacturing defects in a circuit and thereby determine if a given set or program of test patterns (also known as test vectors) can detect an acceptable percentage of faults that may occur in the circuit. Faults that can commonly occur in integrated circuits are metallization runs that are stuck open or stuck shorted. Faults that can occur in printed circuit boards include shorted adjacent runs, shorted adjacent pins, open runs, or shorts to ground or the supply voltage.
In conventional deterministic fault simulation, the simulator creates a faulty circuit by tying the value of pins of circuit elements within a circuit design high or low to insert a single fault for the entire length of a test set. The simulator then applies the set of test vectors chosen by the designer and compares the simulation results for the faulty circuit with that of a fault-free simulation. The inputs of the circuit to which the test vectors are applied are called primary inputs, and the outputs of the circuit from which the results are read are called primary outputs. The primary inputs and primary outputs correspond to the input and output nets or pins of an integrated circuit, respectively, or to the edge connectors and test points of a circuit board. In either case, an inserted fault is considered detected if there is a difference between the logic state of a primary output in the faulty simulation and in the fault-free simulation.
The extent to which a set of test vectors can detect faults is called fault coverage. For example, if a set of test vectors provides 90 percent fault coverage, it can detect 90 percent of all simulated stuck-at-1 and stuck-at-0 faults in the circuit. The extent of fault coverage depends on two factors: the inherent testability of the logic design and the comprehensiveness of the set of test vectors. By continuously improving the design and the set of test vectors and rerunning the fault simulator, a designer can achieve close to 100 percent fault coverage.
Deterministic fault simulation, although exact, demands considerable computing resources. By one study, the CPU time and memory requirements for such fault simulation are proportional to the square of the number of gates in the circuit. This resource demand makes fault simulation a lengthy and costly process for board level design and for designing integrated circuits in the very large scale integrated (VLSI) range.
One approach suggested for reducing the demand on computing resources employs the random sampling of faults. This method simulates a randomly selected subset of faults to give an estimate of the fault coverage. Accuracy of the coverage depends only upon the number of simulated faults, not on the total number of faults in the circuit. Random sampling techniques, however, fall short in that they give no information about the detectability of non-sampled faults.
Another approach is to distribute fault simulation over a number of networked computers. At each computer, a circuit representation is provided with a unique subset of the faults. The faults are thus distributed among multiple copies of the circuit design. The design is then simulated simultaneously on multiple computers. With appropriate partitioning of the faults, the reduction in simulation time is directly proportional to the number of computers.
Despite these approaches for improving fault simulation, the basic deterministic method remains slow and resource intensive. Total CPU time is not reduced but merely distributed over a number of nodes by running portions of the fault simulator simultaneously.
As an alternative to conventional fault simulation, statistical fault analysis has been proposed. Jain and Agrawal, in their article "STAFAN: An Alternative to Fault Simulation," Proceedings of 21st Design Automation Conference, June 1984, pp. 18-23, describe statistical fault analysis as a method of estimating statistically the percent of fault coverage for a given set of test vectors. Instead of running a deterministic fault simulator several times to develop test vectors, statistical fault analysis enables the designer to estimate the fault coverage of a test vector set by statistical calculations. In their study, the described method provided fault coverage within 5 percent of fault simulator results, without the CPU time and memory demands required of deterministic fault simulation. The analysis method is typically rerun several times with additional test patterns until the coverage percentage reaches a desired level. The fault coverage is then verified with a single run through a fault simulator. STAFAN, however, is limited to circuits modeled with basic Boolean gates. If a more complex circuit element such as a multiplexer is to be modeled, it must first be broken down into its basic gate structure. Such a design process places an undue burden on the circuit designer.
The initial work of Jain and Agrawal was advanced by Hi Keung Ma and Alberto L. Sangiovanni-Vincentelli in their article "Mixed-Level Fault Coverage Estimation," Proceedings of the 23rd Design Automation Conference 1986, pp 553-559. There, the authors applied statistical fault analysis to combinational multiple-input, multiple-output functional blocks. With the described method, the circuit designer need only specify the functional relationship between each input and output of the block. For example, if a functional block consists of a multiple gate level combinational circuit element, only the relationship between the inputs and outputs of the circuit must be specified. The Jain method, by contrast, requires that each gate be individually examined.
Despite this advancement, commercial development of statistical fault analyzers has been lackluster. One stumbling block has been the inability to develop a viable method of estimating fault coverage in sequential functional blocks. Sequential circuit elements can be modeled with the methods described above, but only by modeling them as combinational gates or blocks. For example, a D flip-flop must be modeled at its gate level, with statistics generated for each gate within the flip-flop. Caedent Corp. of Colorado Springs, Colo., now owned by the assignee of the present invention, had developed a proprietary method for handling sequential functional blocks. But, the method estimated rather than measured key parameters and required a separate statistical model for each type of sequential functional block. For example, a new type of sequential block employed in a circuit design required that a new statistical model be crafted for that block, based on its internal functionality. The accuracy of the models were difficult to maintain as the models increased in complexity.